package leetcode.od;

import org.junit.Test;

import java.util.Arrays;
import java.util.Scanner;

/**
 * @author pppppp
 * @date 2022/4/14 7:58
 * 输入：
 * 8
 * 186 186 150 200 160 130 197 200
 * 复制
 * 输出：
 * 4
 */
public class HJ24_合唱队 {
    @Test
    public void T_0() {
        int[][] nums = {{1,2,3,2,1},{186, 186, 150, 200, 160, 130, 197, 200}};
        int[] ans = {0,4};
        for (int i = 0; i < nums.length; i++) {
            System.out.println(solution(nums[i]) == ans[i]);
        }
    }

    /*动态规划  最长递增子序列的复用
    划分为 以当前数组结束的最大递增子序列 和 以当前数字开始的最大递减序列*/
    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNext()){
            int len = Integer.valueOf(scanner.nextLine());
            String s = scanner.nextLine();
            String[] split = s.split(" ");
            int[] nums = new int[len];
            for (int i = 0; i < len; i++) {
                nums[i] = Integer.valueOf(split[i]);
            }
            System.out.println(solution(nums));
        }
    }
    private static int solution(int[] num) {
        int max = 0;
        int[] left = getLeft(num);
        int[] right = getRight(num);
        for (int i = 0; i < left.length; i++) {
            max = Math.max(left[i] + right[i] - 1, max);
        }
        return num.length - max;
    }

    private static int[] getRight(int[] num) {
        int[] dp = new int[num.length];
        Arrays.fill(dp, 1);
        for (int i = num.length-2; i >= 0; i--) {
            for (int j = num.length-1; j > i ; j--) {
                if(num[j] < num[i]){
                    dp[i] = Math.max(dp[i],dp[j] + 1);
                }
            }
        }
        return dp;
    }

    private static int[] getLeft(int[] num) {
        int[] dp = new int[num.length];
        Arrays.fill(dp, 1);
        for (int i = 1; i < num.length; i++) {
            for (int j = 0; j < i; j++) {
                if (num[i] > num[j]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
        }
        return dp;
    }
}
